import java.util.*;


class Semantic {
    
    static void error (String s) {
	System.out.println(s);
    }
    
    static boolean checkProgram(Node program) throws SemanticException{
	
	//TODO:Check if the node is a program node.
	if(program.getId() != Id.PROGRAM)
	    return false;
	
	//Create the global environment.
	GlobalEnv globalEnv = new GlobalEnv();
	
	//Program is correct until an error is encountered
	boolean programFlag = true;
	
	int nrOfTopDecs = program.numberOfChildren();
	
        for(int i = 0; i < nrOfTopDecs ; i++)
	    {
		Declaration topDec = (Declaration)program.getChild(i);	 
		Type type;
		String name;
	    int value;
	    
	    switch(topDec.getId())
		{
  	        case VARDEC:
		    {
			TypeNode varTypeNode = (TypeNode)topDec.getChild(0);
			if(varTypeNode.getId() == Id.INT)
			    {
				type = new IntType();
			    }
			else
			    {
				type = new CharType();
			    }
			
		    Identifier idNode = (Identifier)topDec.getChild(1);
		    name = idNode.getName();
		    globalEnv.insert(name, type);
		    break;
		    }    
	        case ARRAYVAR_DEC:
		{
		    TypeNode varTypeNode = (TypeNode)topDec.getChild(0);

		    IntegerLiteral size = (IntegerLiteral)topDec.getChild(2);
		    value = size.getValue();
		    
		    if(varTypeNode.getId() == Id.INT)
		    {
			type = new IntArrayType(value);
		    }
		    else
		    {
			type = new CharArrayType(value);
		    }

		    Identifier idNode = (Identifier)topDec.getChild(1);
		    name = idNode.getName();

		    globalEnv.insert(name, type);
		    break;
		}
  	        case FUNDEC:
		{ 
		    TypeNode funTypeNode = (TypeNode)(topDec.getChild(0));
		    FormalParameters parametersNode = (FormalParameters)topDec.getChild(2);		       
		    
    		    //See if the body isn't empty.
		    LocalEnv localEnv = null;
		    FunctionBody fBodyNode = (FunctionBody)topDec.getChild(4);
		    if(fBodyNode.hasChild())
		    {			
			//Create the local environment for the function body
			localEnv = globalEnv.enter();			

			if(funTypeNode.getId() == Id.INT)
			{
			    type = new IntType();
			}
			else if(funTypeNode.getId() == Id.CHAR)
			{
			    type = new CharType();
			}
			else //void 
			    type = new VoidType();
			
			localEnv.setResult(type);
		    }

		    List<Type> parameters = new ArrayList<Type>();

		    int nrParams = parametersNode.numberOfChildren();
		    for(int j = 0; j < nrParams ; j++)
		    {
			Declaration parameter = (Declaration)parametersNode.getChild(j);
			
			switch(parameter.getId())
			{
			    case VARDEC:
			    {
				TypeNode varTypeNode = (TypeNode)parameter.getChild(0);
				if(varTypeNode.getId() == Id.INT)
				{
				    type = new IntType();
				}
				else
				{
				    type = new CharType();
				}				
				parameters.add(type);

				if(localEnv != null)
				{
				    //Treat the parameter as a local variable.
				    parameter = (VarDeclaration)parameter;
				    Identifier pId = (Identifier)parameter.getChild(1);
				    localEnv.insert(pId.getName(), type);
				}
				
				break;
			    }
			    case ARRAYVAR_DEC:
			    {
			        TypeNode varTypeNode = (TypeNode)parameter.getChild(0);
			    			    
				if(varTypeNode.getId() == Id.INT)
				{
				    type = new IntArrayType();
				}
				else
				{
				    type = new CharArrayType();
				}
			    			    
				parameters.add(type);

				if(localEnv != null)
				{
				    //Treat the parameter as a local variable.
				    parameter = (ArrayVarDeclaration)parameter;
				    Identifier pId = (Identifier)parameter.getChild(1);
				    localEnv.insert(pId.getName(), type);
				}

				break;
			    }
			case VOID:
			    {

			    }
			        break;

			}	    
		    }

		    if(funTypeNode.getId() == Id.INT)
		    {
			type = new IntFunctionType(parameters);
		    }
		    else if(funTypeNode.getId() == Id.CHAR)
		    {
			type = new CharFunctionType(parameters);
		    }
		    else
		    {
			type = new VoidFunctionType(parameters);
		    }

		    Identifier idNode = (Identifier)topDec.getChild(1);
		    name = idNode.getName();

		    globalEnv.insert(name, type);
		    
		    if(localEnv != null)
		    {
			//Process local variables if any.
			LocalVariables localsNode = (LocalVariables)topDec.getChild(3);
			int nrLocals = localsNode.numberOfChildren();
			
			for(int j = 0; j < nrLocals ; j++)
			{
			    Declaration local = (Declaration)localsNode.getChild(j);
			
			    switch(local.getId())
			    {
				case VARDEC:
				{
				    TypeNode varTypeNode = (TypeNode)local.getChild(0);
				    if(varTypeNode.getId() == Id.INT)
				    {
					type = new IntType();
				    }
				    else
				    {
					type = new CharType();
				    }				
				    
				    local = (VarDeclaration)local;
				    Identifier pId = (Identifier)local.getChild(1);
				    localEnv.insert(pId.getName(), type);
				
				    break;
				}
			        case ARRAYVAR_DEC:
				{
				    TypeNode varTypeNode = (TypeNode)local.getChild(0);
			    			    
				    IntegerLiteral size = (IntegerLiteral)local.getChild(2);
				    value = size.getValue();

				    if(varTypeNode.getId() == Id.INT)
				    {
					type = new IntArrayType(value);
				    }
				    else
				    {
					type = new CharArrayType(value);
				    }
			    			    
				    //Treat the local as a local variable.
				    local = (ArrayVarDeclaration)local;
				    Identifier pId = (Identifier)local.getChild(1);

				    localEnv.insert(pId.getName(), type);
				    				    
				    break;
				}
			        case VOID:
				{

				}
			        break;

			    }
			}
			
			//localEnv.print();
			
			//Process statements (the function body isn't empty)
			FunctionBody stmts = (FunctionBody)topDec.getChild(4);
			int nrStmts = stmts.numberOfChildren();
			Statement stmt = null;

			for(int j = 0; j < nrStmts; j++)
			{
			    stmt = (Statement)stmts.getChild(j);			    
			    checkStatement(stmt, localEnv);				
			}
			
			/*
			if(nrStmts>0 && localEnv.getResult().getId() != TypeId.VOID)
			{
			    if(stmt.getId() != Id.RETURN)
			    {
				throw new SemanticException("Return statement is missing");
			    }
			}
			*/
		    }
		    break;	
		}
	    }
	    
	    
	}

	
	/*
	Set<String> env = new HashSet<String>();
	boolean programFlag = true;

	for (Node stmnt : program) {
	    boolean stmntFlag = checkStmnt(stmnt, env);
	    programFlag = programFlag && stmntFlag;
	}
	*/
	
	//globalEnv.print();
	return programFlag;

    }

    static Type checkAssignmentExpression(AssignmentExpression assignment, LocalEnv env) throws SemanticException
    {
	Expression lvalue = (Expression)assignment.getChild(0);
	Expression rvalue = (Expression)assignment.getChild(1);
	BasicIdentifierExpression idExpr;

	//check that is a valid identifier
	try{
	    idExpr = (BasicIdentifierExpression) lvalue;
	}
	catch(ClassCastException e)
	{
	    //lvalue is expected to be a BasicIdentifierExpression
	    throw new SemanticException("Invalid lvalue.");
	}

	Type lvalueType = checkBasicIdentifierExpression(idExpr, env);		
	
	Statement rvalueStmt = (Statement) rvalue;
	Type rvalueType = checkStatement(rvalue, env);

	if(rvalueType.getId() == TypeId.VOID)
	{
	    throw new SemanticException("No rvalue to assign.");	    	    
	}

	if((rvalueType.getId() == TypeId.INT || rvalueType.getId() == TypeId.CHAR) 
	   && (lvalueType.getId() == TypeId.INT_ARR || lvalueType.getId() == TypeId.CHAR_ARR)
	   )
	{
	    throw new SemanticException("Can't assign a value to the array variable .");	    	    
	}

	if((lvalueType.getId() == TypeId.INT || lvalueType.getId() == TypeId.CHAR) 
	   && (rvalueType.getId() == TypeId.INT_ARR || rvalueType.getId() == TypeId.CHAR_ARR)
	   )
	{
	    throw new SemanticException("Can't assign an array to a scalar variable .");	    	    
	}

	if((rvalueType.getId() == TypeId.INT_ARR && rvalueType.getId() == TypeId.CHAR_ARR) 
	   || (lvalueType.getId() == TypeId.CHAR_ARR && lvalueType.getId() == TypeId.INT_ARR)
	   || ( (
		 ((rvalueType.getId() == TypeId.INT_ARR) && (rvalueType.getId() == lvalueType.getId()))
		 ||
		 ((rvalueType.getId() == TypeId.CHAR_ARR) && (rvalueType.getId() == lvalueType.getId()))
		 )
		&& 
		(
		 ((ArrayType)rvalueType).getSize() == ((ArrayType)lvalueType).getSize()
		 ||
		 ((ArrayType)rvalueType).getSize() == 0
	         ||
	         ((ArrayType)lvalueType).getSize() == 0
		)
	   )
	   )
	{
	    throw new SemanticException("Only can convert between arrays that store the same data but have different known dimensions");
	}
	return lvalueType;
 		           
    }

    
    static Type checkAndAndExpression(AndAndExpression expression, LocalEnv env) throws SemanticException
    {
	Statement stmtExpr0 = (Statement) expression.getChild(0);
	Statement stmtExpr1 = (Statement) expression.getChild(1);

	Type expr0Type = checkStatement(stmtExpr0, env);
	Type expr1Type = checkStatement(stmtExpr1, env);

	checkValidOperand(expr0Type);
	checkValidOperand(expr1Type);

	return new IntType();
    }

    static Type checkEqualityExpression(EqualityExpression expr, LocalEnv env) throws SemanticException
    {
	Statement stmtExpr0 = (Statement) expr.getChild(0);
	Statement stmtExpr1 = (Statement) expr.getChild(1);

	Type expr0Type = checkStatement(stmtExpr0, env);
	Type expr1Type = checkStatement(stmtExpr1, env);

	checkValidOperand(expr0Type);
	checkValidOperand(expr1Type);

	return new IntType();
    }

    static Type checkRelationalExpression(RelationalExpression expr, LocalEnv env) throws SemanticException
    {
	Statement stmtExpr0 = (Statement) expr.getChild(0);
	Statement stmtExpr1 = (Statement) expr.getChild(1);

	Type expr0Type = checkStatement(stmtExpr0, env);
	Type expr1Type = checkStatement(stmtExpr1, env);

	checkValidOperand(expr0Type);
	checkValidOperand(expr1Type);

	return new IntType();
    }

    static Type checkAdditiveExpression(AdditiveExpression expr, LocalEnv env) throws SemanticException
    {
	Statement stmtExpr0 = (Statement) expr.getChild(0);
	Statement stmtExpr1 = (Statement) expr.getChild(1);

	Type expr0Type = checkStatement(stmtExpr0, env);
	Type expr1Type = checkStatement(stmtExpr1, env);

	checkValidOperand(expr0Type);
	checkValidOperand(expr1Type);

	/*((expr0Type.getId() == TypeId.CHAR || expr0Type.getId() == TypeId.FUN_CHAR) &&
	   (expr1Type.getId() == TypeId.CHAR || expr1Type.getId() == TypeId.FUN_CHAR))
	    return new CharType);
	    else*/
	return new IntType();
    }

    static Type checkMultiplicativeExpression(MultiplicativeExpression expr, LocalEnv env)  throws SemanticException
    {
	Statement stmtExpr0 = (Statement) expr.getChild(0);
	Statement stmtExpr1 = (Statement) expr.getChild(1);

	Type expr0Type = checkStatement(stmtExpr0, env);
	Type expr1Type = checkStatement(stmtExpr1, env);

	checkValidOperand(expr0Type);
	checkValidOperand(expr1Type);

	/*((expr0Type.getId() == TypeId.CHAR || expr0Type.getId() == TypeId.FUN_CHAR) &&
	   (expr1Type.getId() == TypeId.CHAR || expr1Type.getId() == TypeId.FUN_CHAR))
	    return new CharType();
	    else*/
	return new IntType();

    }

    static void checkValidOperand(Type exprType)  throws SemanticException
    {
	if(exprType.getId() == TypeId.INT_ARR || exprType.getId() == TypeId.CHAR_ARR ||
	   exprType.getId() == TypeId.VOID_FUN || exprType.getId() == TypeId.VOID)
	    throw new SemanticException("Invalid operand.");	    
    }

    static Type checkUnaryExpression(UnaryExpression expr, LocalEnv env) throws SemanticException
    {	
	Statement stmtExpr = (Statement) expr.getChild(0);
	Type exprType = checkStatement(stmtExpr, env);

	checkValidOperand(exprType);

	switch(exprType.getId())
	    {
	    case INT:
		return new IntType();
	    case CHAR:
		return new CharType();
	    case INT_FUN:
		return new IntType();
	    case CHAR_FUN:
		return new CharType();
	    default:
		throw new SemanticException("Invalid unary expression.");
	    }

    }

    static Type checkBasicExpression(BasicExpression expr, LocalEnv env) throws SemanticException
    {
	switch(expr.getId())
	{
	    case IDENTIFIER:
		BasicIdentifierExpression idExpr = (BasicIdentifierExpression) expr;
		return checkBasicIdentifierExpression(idExpr,env);
		
	    case INTEGER_LITERAL:	
		return new IntType();

	    case FUNCALL:
		FunctionCall fCall = (FunctionCall) expr;
		return checkFunctionCallExpression(fCall, env);
	    default:
		throw new SemanticException("Invalid basic expression");
	}

	
    }
    

    static Type checkFunctionCallExpression(FunctionCall fCall, LocalEnv env) throws SemanticException
    {
	//Finished, not tested.
	Identifier fId = (Identifier)fCall.getChild(0);
	ActualParameters aParams = (ActualParameters)fCall.getChild(1);
	String fName = fId.getName();
	Type fType = env.lookup(fName); //check the name
	    
	if(fType == null)
	    throw new SemanticException("Function " + fName +" has not been defined.");
	else
	{	    
	    if(fType.getId() == TypeId.INT_FUN || fType.getId() == TypeId.CHAR_FUN || fType.getId() == TypeId.VOID_FUN)
	    {
	     
		FunctionType funType = (FunctionType) fType;
		List<Type> parameters = funType.getParameters();
		int nrActualParams = aParams.numberOfChildren();
		int nrParameters = parameters.size();
		if(nrActualParams != nrParameters)
		    {
			throw new SemanticException(fName + " takes " + nrParameters +  " parameters.");
		    }
		
		for(int i=0; i < nrActualParams; i++)
		    {
			Type aParamType = checkStatement((Statement)aParams.getChild(i), env);
			Type paramType = parameters.get(i);
			
			if((aParamType.getId() == TypeId.INT_ARR && paramType.getId() == TypeId.CHAR_ARR) ||
			   (aParamType.getId() == TypeId.CHAR_ARR && paramType.getId() == TypeId.INT_ARR) ||
			   (aParamType.getId() == TypeId.VOID_FUN)
			   )
			    throw new SemanticException(fName + " takes wrong  parameters.");
		    }

		if(fType.getId() == TypeId.INT_FUN)
		    fType = new IntType();
		else if(fType.getId() == TypeId.CHAR_FUN)
		    fType = new CharType();
		else 
		    fType = new VoidType();
	    }
	    else
		throw new SemanticException(fName + " is not a function.");
	}

	return fType;	
    }

    static Type checkBasicIdentifierExpression(BasicIdentifierExpression idExpr, LocalEnv env) throws SemanticException
    {
	Type idType = env.lookup(idExpr.getName());
	
	if(idType == null)
	    {
		throw new SemanticException(idExpr.getName() + " has not been defined");
	    }
	else if(idType.getId() == TypeId.INT_ARR || idType.getId() == TypeId.CHAR_ARR)
	    {
		//Check that the expresssion between brackets isn't void (if any)
		try
		{
		    ArrayIdentifierExpression arrayIdent = (ArrayIdentifierExpression) idExpr;

		    //modified by Tong, we should also check the expresion between bracks
		    Statement indexStatement = (Statement) arrayIdent.getChild(0);
		    Type indexType = checkStatement(indexStatement, env);
		    
		    if (indexType.getId() == TypeId.VOID) {
			 throw new SemanticException("An index type should be an integer");
		    }

		    if(idType.getId() == TypeId.INT_ARR)
			idType = new IntType();
		    else
			idType = new CharType();
		}
		catch(ClassCastException e)
		{
		    //The identifier is an array, but it was used without brackets, probably as a parameter in a function call.
		    //Just return its type.
		}
		
	    }
 	else if(idType.getId() == TypeId.INT || idType.getId() == TypeId.CHAR)
	{
	    try
		{
		    ArrayIdentifierExpression arrayIdent = (ArrayIdentifierExpression) idExpr;
		    //Is the identifier treated as an array?
		    throw new SemanticException(idExpr.getName() + " is not an array");
		}
		catch(ClassCastException e)
		{
		    //Expected
		}
	}
	
	return idType;		
    }


    static Type checkExpression(Expression stmt, LocalEnv env) throws SemanticException
    {
	Type type;
	switch(stmt.getId())
	{
	    case ASSIGNMENT:
	    {
		//System.out.println("Checking assignment...");
		AssignmentExpression assignment = (AssignmentExpression) stmt;
		type = checkAssignmentExpression(assignment, env);
		//System.out.println("..assignment is correct.");		
		break;
	    }
	    
	    case ANDAND:
	    {
		//System.out.println("Check andand...");
		AndAndExpression expr = (AndAndExpression) stmt;
		type = checkAndAndExpression(expr, env);
		//System.out.println("..andand is correct.");		
		break;
	    }
	    
	    case RELOP:
	    {
		//System.out.println("Check relop...");
		RelationalExpression expr = (RelationalExpression) stmt;
		type = checkRelationalExpression(expr, env);
		//System.out.println("..relop is correct.");		
		break;
	    }
	    
	    case ADDOP:
	    {
		//System.out.println("Check addop...");
		AdditiveExpression expr = (AdditiveExpression) stmt;
		type = checkAdditiveExpression(expr, env);
		//System.out.println("..addop is correct.");		
		break;
	    }
	    
	    case MULOP:
	    {
		//System.out.println("Check mulop...");
		MultiplicativeExpression expr = (MultiplicativeExpression) stmt;
		type = checkMultiplicativeExpression(expr, env);
		//System.out.println("..mulop is correct.");		
		break;
	    }
	    
	    case UNOP:
	    {
		//System.out.println("Check unop...");
		UnaryExpression expr= (UnaryExpression) stmt;
		type = checkUnaryExpression(expr, env);
		//System.out.println("..unop is correct.");		
		break;
	    }
	    
	    case EQOP:
	    {
		//System.out.println("Check eqop...");
		EqualityExpression expr= (EqualityExpression) stmt;
		type = checkEqualityExpression(expr, env);
		//System.out.println("..eqop is correct.");		
		break;
	    }	

	    case IDENTIFIER:
	    case INTEGER_LITERAL:   
	    case FUNCALL:
	    {
		//System.out.println("Check basic expression...");
		BasicExpression expr= (BasicExpression) stmt;
		type = checkBasicExpression(expr, env);
		//System.out.println("..basic expression is correct.");		
		break;	    
	    }

	    default:
		throw new SemanticException("Wrong type of expression.");

	}

	return type;
    }

    static void checkWhileStmt(WhileStatement wStmt, LocalEnv env) throws SemanticException
    {
	Statement condition = (Statement) wStmt.getChild(0);
	Statement stmt = (Statement) wStmt.getChild(1);	

	Type conType = checkStatement(condition, env);
	checkValidOperand(conType);
	Type stmtType = checkStatement(stmt, env);
	
    }

    static void checkIfStmt(IfStatement ifStmt, LocalEnv env) throws SemanticException
    {
	Statement condition = (Statement) ifStmt.getChild(0);
	Type conType = checkStatement(condition, env);
	checkValidOperand(conType);

	Statement stmt = (Statement) ifStmt.getChild(1);	
	Type stmtType = checkStatement(stmt, env);
	
	try {
	    stmt = (Statement) ifStmt.getChild(2,3);
	    stmtType = checkStatement(stmt, env);
	}
	catch (IllegalArgumentException e){
	    //it is a if statement without mathced else
	}	   
    }

    static void checkElseStmt(ElseStatement elseStmt, LocalEnv env) throws SemanticException
    {
	Statement stmt = (Statement) elseStmt.getChild(0);	
	Type stmtType = checkStatement(stmt, env);       
    }

    static void checkCompoundStamt(CompoundStatement cmpStmt, LocalEnv env) throws SemanticException
    {
	int nrOfStmts = cmpStmt.numberOfChildren();

        for(int i = 0; i < nrOfStmts ; i++)
	{
	    Statement stmt = (Statement)cmpStmt.getChild(i);
	    checkStatement(stmt, env);
	}
    }

    static void checkReturnStatement(ReturnStatement rStmt, LocalEnv env) throws SemanticException
    {       
	Type returnType = env.getResult();

	if(rStmt.numberOfChildren()==0 && returnType.getId() != TypeId.VOID)
	{
	    throw new SemanticException("The function isn't void but retuns nothing");	    
	}

	if(rStmt.numberOfChildren()>0)
	{
	    if(returnType.getId() == TypeId.VOID)
		throw new SemanticException("The function is void but it returns something");
	    else
	    {
		Statement stmt = (Statement)rStmt.getChild(0);
		Type t = checkStatement(stmt,env);
		if(t.getId() == TypeId.VOID_FUN || t.getId() == TypeId.INT_ARR || t.getId() == TypeId.CHAR_ARR)
		{
		    throw new SemanticException("The function returns an invalid type.");
		}		    
	    }
	}      
    }
    
    static Type checkStatement(Statement stmt, LocalEnv env) throws SemanticException
    {
	Type type = null;

	switch(stmt.getId())
	{    
	    case WHILE:
	    {
		//System.out.println("Checking while...");
		WhileStatement wStmt = (WhileStatement) stmt;
		checkWhileStmt(wStmt, env);
		//System.out.println("... while checked");
		break;
	    }
	    
	    case IF:
	    {
		//System.out.println("Checking if...");
		IfStatement ifStmt = (IfStatement) stmt;
		checkIfStmt(ifStmt, env);
		//System.out.println("... if checked");
		break;
	    }
	    
	    case ELSE:
	    {
		//System.out.println("Checking else...");
		ElseStatement eStmt = (ElseStatement) stmt;
		checkElseStmt(eStmt, env);
		//System.out.println("... else checked");
		break;
	    }

	    case COMPOUND_STATEMENT:
	    {
		//System.out.println("Checking compound statement...");
		CompoundStatement cStmt = (CompoundStatement) stmt;
		checkCompoundStamt(cStmt, env);
		//System.out.println("... compound statement checked");
		break;
	    }
	    
	    case RETURN:
	    {
		//System.out.println("Checking return statement...");
		ReturnStatement rStmt = (ReturnStatement) stmt;
		checkReturnStatement(rStmt, env);
		//System.out.println("... return statement checked");
		break;
	    }

	   default:
	       //System.out.println("Checking expression statement...");
	       Expression expr = (Expression)stmt;
	       type = checkExpression(expr, env);	    
	       //System.out.println("... expression statement checked");
	}

	return type;
    }
    
    /*
    static boolean checkStmnt (Node stmnt, Set<String>env) {
	
	switch (stmnt.getId()) {
	case ASSIGN :
	    IdentifierNode var = (IdentifierNode)stmnt.getChild(0, 2);
	    Node exp = stmnt.getChild(1, 2);
	    
	    boolean flag = checkExp(exp, env);

	    env.add(var.getName());
	    
	    return flag;

	default :
	    error("Unexpected statement: "+stmnt.getId());
	    return false;
	}
    }


    static boolean checkExp (Node exp, Set<String> env) {
	
	switch (exp.getId()) {

	case DOUBLE :
	    return true;

	case IDENT :
	    String name = ((IdentifierNode)exp).getName();
	    if (env.contains(name)) return true;
	    
	    error("Variable " + name + " not defined.");
	    return false;
	    
	case PLUS :
	    boolean flag1 = checkExp(exp.getChild(0,2), env);
	    boolean flag2 = checkExp(exp.getChild(1,2), env);
	    return flag1 && flag2;

	default :
	    error("Unexpected expression: "+exp.getId());
	    return false;
	}
    }
    */
}



